package com.rd.teacher.jichao.day01;

/*
4、编写一个质数类Prime/praɪm/ Number，质数类提供了一个方法isPrime()，
可以通过传入一个整数num，返回它是否为质数。
编写完成后，在main方法中创建Scanner类的实例，调用isPrime()方法测试其效果。
 */
public class PrimeNumber {

    public static void main(String[] args) {
        System.out.println(isPrime(10));
    }

    public static boolean isPrime(int num) {
        // num 是否是质数/素数
        // 定义： 只能被1和它自身整除的数
        //       一旦被除了这两个数之外的数整除了   就不是质数了
        // [1,num]   范围内的值 去和num自身整除进行判断
        //  10  -> [1,10]  -> [2,9]   缩小范围为 [2,num-1]   [2,num)
        //        「整除」 10%2=0  10%3=1 10%4=2  整除等价于 取余结果为0
        //     [2,9]    10%2=0  直接返回否 「10不是质数」
        //  3   -> [2]    3%2=1    遍历完成返回是 「3是质数」
        //  5   -> [2,4]   5%2=1   5%3=2  5%4=1

        if(num <= 1)  return false;
        // 如果传来的是num=1  会进入循环吗
        for (int i = 2; i < num; i++) {
            // num=10  2,3,4 ... 9
            int tmp = num % i;
            if(tmp == 0) {
                // 一旦被除了这两个数之外的数整除了   就不是质数了
                return false;
            }
        }

        // 当循环结束  [2,num-1]被取余结束  没有被其中任何一个值整除
        return true;
    }


    public static boolean isPrime1(int num) {
        // 11 -> [2,10]
        //       11%2  11%3  11%4  11%5  11%6   11%7  11%8  11%9
        //      如果11%2 和 11%9 能被整除  都会被整除
        //      如果11%2 和 11%9 不能被整除  那么都不能被整除
        //          11%2 = 1   11%9 = 2
        // 9 -> [2,8]   -> [2,4] / [2,5]
        //       9%2 9%3 9%4 9%5 9%6 9%7  9%8
        //        1   0   1   4   3   2    1
        //      9%2 和 9%7
        //      9%3 和 9%6

        //   如果num能够被这个范围内的一个值整除 那么一定会出现在前半段
        //   如果前半段没出现  后半段也不会再出现了
        // 7 -> [2,6]
        //      7%2 7%3 7%4 7%5 7%6

        if(num <= 1)  return false;
        for (int i = 2; i <= num/2; i++) {
            int tmp = num % i;
            if(tmp == 0) {
                return false;
            }
        }

        return true;
    }

    // 将范围进一步缩小为 num的平方根
    public static boolean isPrime2(int num) {
        // 11 -> [2,10]  -> [2,5]
        //       11%2  11%3  11%4  11%5  11%6   11%7  11%8  11%9
        //      如果11%2 和 11%9 能被整除  都会被整除
        //      如果11%2 和 11%9 不能被整除  那么都不能被整除
        //          11%2 = 1   11%9 = 2
        // 9 -> [2,8]   -> [2,4] / [2,5]
        //       9%2 9%3 9%4 9%5 9%6 9%7  9%8
        //        1   0   1   4   3   2    1
        //      9%2 和 9%7
        //      9%3 和 9%6
        // 25 -> [2,12]    [2,num/2]
        //       25%2 25%3 25%4 25%5 25%6 25%7 25%8 25%9 25%10 25%11 25%12
        //                        0

        if(num <= 1)  return false;
        int sqrt = (int)Math.sqrt(num);
        for (int i = 2; i <= sqrt; i++) {
            int tmp = num % i;
            if(tmp == 0) {
                return false;
            }
        }
        return true;
    }

}
